
'''
五种排序方式
时间复杂度:增加循环次数，增减的总的次数情况O(n)
空间复杂度：增加循环次数，增加的内存空间使用情况O(1)
'''

# 冒泡排序，像同学按身高要求一一比对排队
def buddle_sort(array):
    lens=len(array)
    # 外层控制循环次数，内层控制排序次数
    for i in range(1,lens):
        for j in range(0,lens-i):
            if array[j]>array[j+1]:
                array[j],array[j+1]=array[j+1],array[j]
    return array


def buddle_sort1(array):# 并非插入排序
    lens=len(array)
    # 外层控制循环次数，内层循环控制比较次数
    for i in range(1,lens):
        for j in range(i):
            if array[j]>array[j+1]:
               array[j],array[j+1]=array[j+1],array[j]
    return array

# 插入排序--打牌从小到大排序一样插入纸牌
#将序列的第一个元素当做已经排序好的序列，然后从后面的第二个元素开始，逐个元素进行插入，直到整个序列有序为止。
def insert_sort(array):
    for i in range(1,len(array)):
        key=array[i]
        j=i-1
        while j>=0 and key<array[j]:
            array[j+1]=array[j]
            j-=1
        array[j+1]=key
    return array
# 选择排序，首先选择最小排数在1的位置，依次查找第二小的数在2的位置，直到查找完成
def select_sort(array):
    lens=len(array)
    for i in range(lens):
        min=i # 假设i最小，和最小进行比较
        for j in range(i,lens-1):
            if array[j]<array[min]:
                min=j
        array[i],array[min]=array[min],array[i]
    return array

# 快速排序,分治思想
#设置一个基准元素，一般是第一个或者最后一个，将序列以该基准元素为基准，分割成比他小的一部分和比他大的一部分，不断递归,最后组合成一个有序数据
def quick_sort(array):
    if array==[]:
        return []
    else:
        first=array[0]
        left=quick_sort([i for i in array[1:] if i<=first])
        right=quick_sort([j for j in array[1:] if j >first])
        return left+[first]+right

# 堆排序


# 归并排序，分治思想，先拆开，在合并起来
def merge_sort(array):
    if len(array)<1:
        return array
    mid=len(array)//2
    # 先拆分成一个一个的元素
    left,right=merge_sort(array[:mid]),merge_sort(array[mid:])
    # 合并函数
    return merge(left,right,array.copy())

def merge(left,right,merged):
    left_cursor,right_cursor=0,0
    # 单只是单独一个元素时
    while left_cursor<len(left) and right_cursor<len(right):
        if left[left_cursor]<=right[left_cursor]:
            merged[left_cursor+right_cursor]=left(left_cursor)
            left_cursor+=1
        else:
            merged[left_cursor+right_cursor]=right[right_cursor]
            right_cursor+=1
    for left_cursor in range(left_cursor,len(left)):
        merged[left_cursor+right_cursor]=left[left_cursor]
    for right_cursor in range(right_cursor,len(right)):
        merged[left_cursor+right_cursor]=right[right_cursor]
    return merged
# 归并排序2
# def merge_sort1(array):
#     def merge_arr(arr_l, arr_r):
#         array = []
#         while len(arr_l) and len(arr_r):
#             if arr_l[0] <= arr_r[0]:
#                 array.append(arr_l.pop(0))
#             elif arr_l[0] > arr_r[0]:
#                 array.append(arr_r.pop(0))
#         if len(arr_l) != 0:
#             array += arr_l
#         elif len(arr_r) != 0:
#             array += arr_r
#         return array

if __name__ == '__main__':
    a=[1,3,4,2,5,12,9,34,1,-1,20,-5,0,9]
    print(buddle_sort(a))
    print(insert_sort(a))
    print(select_sort(a))
    print(quick_sort(a))
    print(merge_sort(a))
    pass